from math import inf

def dijkstra_recursion(graph,start,distances,path):
    n=len(graph)
    weights=graph[start]
    for i in range(n):
        distance=weights[i]+distances[start]
        if distance < distances[i]:
            distances[i]=distance
            path[i]=start
            dijkstra_recursion(graph,i,distances,path)

def dijkstra(graph,start):
    n=len(graph)
    distances=[inf]*n
    distances[start]=0
    path=[-1]*n
    dijkstra_recursion(graph,start,distances,path)
    return f'{distances}\n{path}'

graph=[
    [0,2,6,inf,inf,inf,inf],
    [2,0,inf,5,inf,inf,inf],
    [6,inf,0,8,inf,inf,inf],
    [inf,5,8,0,10,15,inf],
    [inf,inf,inf,10,0,6,2],
    [inf,inf,inf,15,6,0,6],
    [inf,inf,inf,inf,2,6,0]
]

print(dijkstra(graph,0))
